#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0006.py
@time: 2021/9/8 12:09
@desc: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
'''
class Solution:
    def validateStackSequences(self, pushed: list, popped: list) -> bool:
        stack, i = [], 0

        for num in pushed:
            stack.append(num)
            # stack出现poped的元素时就弹出
            while len(stack)>0 and stack[-1]==popped[i]:
                stack.pop()
                i += 1

        # 判断能否弹出所有即可知道是否合法
        return len(stack)==0

if __name__ == '__main__':
    s = Solution()
    pushed = [1,2,3,4,5]
    popped = [4,3,5,1,2]

    t = s.validateStackSequences(pushed, popped)